#pragma once

#include <queue>
#include <vector>

namespace solution_429
{

class Node
{
public:
    int val;
    std::vector<Node*> children;
    Node() { }
    Node(int _val) : val(_val) { }
    Node(int _val, std::vector<Node*> _children) : val(_val), children(_children) {}
};

class Solution
{
public:
    std::vector<std::vector<int>> levelOrder(Node* root)
    {
        std::vector< std::vector<int> > levels;
        if (root == nullptr)
            return levels;

        std::queue<Node*> queue;
        queue.push(root);
        int last_level_size = queue.size();
        while (!queue.empty()) {
            levels.emplace_back();
            for (int i = 0; i < last_level_size; ++i) {
                levels.back().push_back(queue.front()->val);
                for (auto node : queue.front()->children)
                    queue.push(node);
                queue.pop();
            }
            last_level_size = queue.size();
        }

        return levels;
    }
};

}  /* namespace 429 */
